package org.leetcode.easy.leetcode69;

public class Solution
{
    public static int mySqrt(int x)
    {

        if (x==0 || x==1)
        {
            return x;
        }

        double num  = x ;

        for (int i =1;i<=x/2;i++)
        {
            if (i<=num/i && (i+1)>num/(i+1))
            {
                return i;
            }

        }
        return x;
    }

    //二分查找法
    public static int mySqrt2(int x)
    {
        if (x==0 || x==1) {
            return x;
        }

        int left =1,right =x/2;

        while (left<=right)
        {
            int mid =(left+right)>>>1;

            if (mid<=x/mid && (mid+1)>x/(mid+1))
            {
                return mid;
            }else if (x/mid<mid)
            {
                right=mid-1;
            }else {
                left=mid+1;
            }
        }

        return left;
    }

    public static void main(String[] args) {
        int i = mySqrt2(10);
        System.out.println(i);
    }
}
